The Eating Club

Whole groups of people want to keep track of what they eat and to compare progress. This case study describes extensions to the You Are What You Eat and You Forgot What You Ate programs to handle a complex food list, multiple users, and several reporting formats. The program should be able to sort foods and entries and do it quickly.

Problem Statement

Terry calls us a couple of weeks after we give him the You Forgot What You Ate programs. Here is the conversation:

TERRY: A group of my friends and I have been comparing our progress in controlling our diets. I showed the program to them and they want to use it too. Is that OK?

MIKE AND MARCIA: Probably. What were the reactions of your friends?

TERRY: Well, they were excited. For example, my friend Erin has been looking for a program like this. She has lots of computer experience. She did say that the program is a bit slow. Is that what you mean?

MIKE AND MARCIA: We aren't surprised. Our goal was to put the program together quickly. We could make it more efficient.

TERRY: Well, that would make Erin happy.

MIKE AND MARCIA: Were there other comments?

TERRY: Well, several of us have been competing to see who can bring down their calories and fat intake the most. We'd like to compare our graphs. It would be easier if the graphs were all on the same scale. Is that possible?

MIKE AND MARCIA: That would be straightforward. We'd need to know what scales make sense. Are there different scales for men and women, for example?

TERRY: Maybe the program could just ask us for the maximum and minimum values for the graphs? See, I'm getting the idea of this user interface stuff!

MIKE AND MARCIA: Sounds good. Any other comments?

TERRY: One of my friends is from India. She eats some foods that aren't on the food list. Is there a way to add foods to the list?

MIKE AND MARCIA: That would be possible. What did you have in mind? Would each person have an individual food list or do you want to add the foods that everyone eats to a general list?

TERRY: We'd like to have a general list. Sometimes my friend invites all of us over for dinner so we all need these foods on our lists.

MIKE AND MARCIA: We will work on that. We'll get back to you in a few days.

TERRY: Thanks.

Analysis

12.1 What else should we have asked Terry?

Analysis

12.2 In what other ways might the program be customized or improved? Explain.

Reflection

12.3 How would you look for parts of a program that you could rewrite to be more efficient?

Reflection

12.4 We were somewhat reluctant to distribute our program to a large number of people before we worked on improving its efficiency. Suppose you had quickly put together a program for a friend. What aspects of the program would you have to fix before you would distribute it to a wider audience? Explain

Analysis

12.5 It appears that Terry's friends will each use separate copies of the program and its associated data files. What arrangements should they make to ensure that they have the most up-to-date version of the food file?

Analysis

12.6 If Terry and his friends were intending to use the same copy of the program, how would the revisions he requested be different?

Analysis

12.7 Suppose that Terry and one of his friends have the same name for two different foods. For instance, the milk and flavoring combination that people in Massachusetts call a milk shake is a different nutritional story from the milk, flavoring, and ice cream combination that other people in the United States call a milk shake. (People in Massachusetts call the ice cream version a frappe!) How should this problem be handled?

Preparation

The reader should be familiar with files, arrays, and dictionaries, as well as the use of recursion.

Improvements to You Forgot What You Ate

What changes are desired?

The program would be more useful for Terry and his friends with three main changes. First, it needs to be more efficient. We knew the program wasn't too efficient, but we wanted to get it to work first. Now that the users are excited about it, it makes sense to improve its efficiency.

Second, the program needs to make it easier for users to compare progress. Terry did not mention this before so this is a new specification. We are happy to see that Terry is getting more sophisticated; he even suggested the option of asking the user for the maximum and minimum values for each graph.

Stop & Predict

What if the users forget the graph values they agreed on?

We wonder if users will remember what values they all want to use. It would be better to supply some built-in default options if the user has no particular values in mind.

Third, the users need to be able to update the food list. We are immediately reminded of the history file editing program. We should be able to use the same approach for updates to the food file.

How are the graphing routines changed?

Fixing the graphs seems easiest, so we do that first. Two steps must be added to the graph printing functions: one that asks the user for the maximum and minimum values over which the graph will be plotted, and one that computes reasonable values to use if the user doesn't have any specific ones picked out. The actual maximum and minimum data values are the obvious "reasonable" values; after some reflection, we decide to round them up (for the maximum) or down (for the minimum) to the next multiple of 100 to make the graph look nicer.

How are good default graph bounds computed?

Computing the maximum and minimum array values is straightforward. Rounding up or down is somewhat tricky. To compute the next lower multiple of 100, we replace the last two digits with zeroes as follows:

nextLower100 = (value // 100) * 100

To compute the next higher multiple of 100, we add 1 to the hundreds place and replace the last two digits with zeroes, unless they are already zero.

if value % 100 == 0:
nextHigher100 = value
else:
nextHigher100 = ((value // 100) + 1) * 100

Reading the values from the user can be done in PrintFatGraph and PrintCalorieGraph as follows. First, each can compute the default maximum and minimum values as just described. Then, each can call a Readinteger function with the default value as an argument. If the user types an integer, it's returned; if the user types a blank line-merely hits "return" on the keyboard the default value is returned and used in the graph.

How is the code tested?

All this code can be added to the program and tested immediately. We can create test files with the history file editor; thorough tests will ensure that both outcomes of the if statement above are exercised.

How can programs be made to run more quickly?

We can speed up a program by identifying and replacing slow operations. For instance, file operations are slow; it typically takes a thousand times longer to read an integer from a disk file than to copy an integer value into a variable. Thus code that reads information from a file into a large array and works on it there will be more efficient than code that reads through the file several times to perform its operations.

Stop & Help

Roughly how long does it take to read an integer from a disk file on your computer?

Of course, we can also speed up a program if we reduce the number of operations it has to perform. For instance, the single statement

print("{1:24d}".format(A))

will probably be executed more quickly than the equivalent segment

for k in range(23):
print(BLANK)
print('A')

Another example appears in the Equal function in the You Are What You Eat program:

Equal = True
for k in range(line["length"]):
if line["chars"][k] != s[k]:
Equal = False

This could be recoded as a while loop, so that the loop would terminate as soon as a nonmatching character was found:

k = 1
if line["length"] == 0:
Equal = True
else:
while (k < line["length"]) and (line["chars"]
[k] == s[k]):
k = k + 1
Equal = line["chars"][k] == s[k]

Suppose that both line and s are 10 characters long, and the first characters of line and s don't match. Then the first loop would perform 11 comparisons of k with line["length"] (hidden in the operation of the for loop), 11 increments of k, and 10 comparisons of characters in line with characters in s. The second loop would perform 1 comparison of k with line["length"], 1 increment of k, and 2 comparisons of line["chars"] with s[1].

Stop & Predict

How many operations are likely to be saved by these revisions to the code?

What good does rewriting code details do?

Rewriting code details will probably not make much difference in the speed of the program, however. In You Are What You Eat, the Equal function is called once for each fat value read, to check for the done sentinel. Eliminating 20 comparisons and 10 increments, each of which probably takes less than a microsecond, saves 30 microseconds not a savings that Erin would appreciate.

Furthermore, the rewritten code is more complicated and likely to have errors. Programmer efficiency is important too.

Thus we target our attention on parts of the program where rewriting code is likely to make a big difference. In the programs for You Forgot What You Ate, this means examining areas where large numbers of operations are performed for each user input. Assuming that the data collection program is run much more often than the history editor, we focus on it.

Where in the program will optimizing prove most beneficial?

It will help to review the program's call diagram:

Initialize, Update, PrintAverages, and PrintGraphs are each called exactly once from the main program. FatAverage and CalorieAverage are called just once from PrintAverages, and PrintFatGraph and PrintCalorieGraph are called just once from PrintGraphs. FindSuccessor, WritelnDate, and ReadEntry are called once from Initialize. ReadFood and ReadServings are called once for each entry read from the user.

Equal is called once for each entry, as it was in You Are What You Eat. In the revised version in You Forgot What You Ate, however, it is also called once for each comparison between the input food and the entries in the food information file. The food file contains entries for roughly 800 foods. Here is a chance to reduce the program running time, since any improvement will be multiplied several hundred times.

We can rewrite Equal, as described above, so that it stops comparing when encountering a character mismatch in its two arguments. This should save some time, since almost all the comparisons will be between strings that differ.

Stop & Help

Test the program with Equal rewritten as described above. Do you notice any difference in the running time?

Another source of inefficiency is that Search searches the food file for every user entry. It would be better, as mentioned earlier, to read the file once into an array and then search the array instead of the file. The size of the food file can be established in advance, so the bounds of the array will be known. We add an InitFoodInfo function to the program, call it from Initialize, and modify Search accordingly. (Changes to parameter lists of other subprograms are also necessary. This could have been avoided by better planning during the initial design of the program.)

Stop & Help

Test the program with the changes just described. Do you notice any difference in the running time?

The actual search of the food information is also a good place to increase efficiency. What do humans do to make searches efficient? Consider large directories of entries that people use, like phone books. A person looking up a phone number doesn't search linearly through the phone book, but instead goes to the approximate section of the name list and examines only a few pages.

How can the search for a food name be sped up?

The key to the efficient phone book search is that the names are alphabetically ordered. Ordering a list of entries can result in efficient program search as well. Though a program may not be able to go directly to the approximate location of a name as humans do with phone books, a systematic approach called binary search can be applied that's almost as effective.

Stop & Consider

How do humans play the game of 'guess my number' efficiently? In this game the guesser can ask questions with yes or no answers, such as "Is the number greater than 100?"

How does the binary search algorithm work?

The binary search algorithm is used to search for an item in an array of elements. The elements of the array must be ordered so that one can tell when one item is less or greater than another. The algorithm continuously reduces the range of elements in which the item can be found. This range is identified by two indices into the array, low (the smallest position at which the item can occur) and high (the largest position at which the item can occur). Thus if low contains 5 and high contains 27, the item being sought can be in positions 5 through 27 of the array but cannot be in positions 1 through 4 or in a position later than 27.

Just as in a number guessing game, the most efficient way to search a range of values is to eliminate half of them with each query. Thus the binary search algorithm repeats the following process.

Find the middle element in the range low ... high.
Compare the item being sought with the middle element.
If it's equal, indicate a successful search, and return the position of the middle element.
If the item is less than the middle element, then it can't be in any of the positions from the middle to the end; thus the high end of the range is moved down to one prior to the middle position.
If the item is greater than the middle element, it can only be in the top half of the range; thus the low end of the range is moved up to one following the middle position.

The process terminates when the item is found or when the range shrinks to nothing, that is, when high is less than low. Figure 12.1 shows how the algorithm proceeds to locate element 350 in an array of 800 elements.

Finding the 350th element using a linear search algorithm would have required 349 unsuccessful comparisons; with binary search, it required only four. Since the range of elements to examine is cut in half at each iteration, the largest possible number of comparisons is the number of times one can cut the range in half and still have some left. The mathematical expression for the amount one can cut a range of N elements in half is log₂ N (the base 2 logarithm of N). For an array of 800 elements, at most 10 comparisons are needed to find any element.

This algorithm can be implemented with a loop or with recursion. The two implementations, one using a loop and the other recursive, appear below.

# version using a loop

def Search(line, foodinfo, foodEntry, found):
low = 1
high = FOODINFOSIZE
middle = 0
found = False
while not found and (high >= low):
middle = (low + high) // 2
if Equal (line, foodinfo[middle] .foodName):
found = True
foodEntry = foodinfo[middle]
elif LessThan (line, foodinfo[middle] .foodName):
high = middle - 1
else:
low = middle + 1

# (recursive version)

def SearchHelper(line: LineType, low: int, high: int):
global foodInfo
global foodEntry1
global found1
found = False
found1 = False
if high < low:
found = False
else:
middle = (low + high) // 2
found = Equal (line, foodInfo. foods
[middle].foodName)
if found:
foodEntry1 = foodInfo.foods[middle]
found1 = True
return found1
else:
if LessThan (line, foodInfo.foods
[middle].foodName):
SearchHelper (line, low, middle - 1)
else:
SearchHelper (line, middle + 1, high)

def RecursiveSearch (line, foodinfo, foodEntry, found):
SearchHelper (line, foodinfo, foodEntry, found,
1, FOODINFOSIZE);

Both versions use a LessThan function that does not currently exist. The code can be patterned on that of Equal, however.

Stop & Consider

Which of these solutions is easier to understand?

How can this algorithm be applied to the food information?

Binary search requires an ordered array. Since food names are to be looked up, the names in the array should be in alphabetical order. The file we provided Terry isn't in order, so we have to sort its entries.

We might be tempted to sort the food file every time the program is run, since we plan to allow users to add foods. This would be needless work, however; the code that adds food information can be written to put it in the correct place in the file, maintaining an ordered food file just as the history editor currently maintains an ordered history file. Thus the file needs to be sorted only once, so we'll write a separate program to do that.

How should the food information file be sorted?

There are many ways to sort, and entire books have been written on the subject. We might look up a sorting function in one of the books. Alternatively, we can design our own, based on ideas from earlier case studies. The Shuffler's Dilemma discussed three approaches to "disordering" cards by shuffling them: selection, exchange, and insertion. All three approaches also form the basis of sorting functions.

Sorting by selection: Repeatedly choose the smallest value left in the array, remove it from the unsorted array, and add it to the end of the sorted array until no more elements remain in the unsorted array.

Sorting by insertion: Repeatedly take the next value in the unsorted array and insert it in its proper position in the sorted array.

Sorting by exchanging: Repeatedly choose two array elements and exchange them if they are out of order.

We'll consider the first two of these approaches here (leaving the third for consideration in study questions).

How does selection sorting work?

A function called Selection Sort may be represented by the following pseudocode:

def SelectionSort (unsorted, sorted):
k = 0
for k in range (1 to the number of array elements):
find the smallest value remaining in unsorted,
remove it, and store it in sorted[k]

The code framework is similar to Efficient Selection Shuffle. It uses the "process every element in an array" template. The difference between this code and Efficient Selection Shuffle is that the elements are processed in a different order.

Finding the smallest value remaining in unsorted will be easier if all the elements of unsorted are stored together. If we ensure that removal of an element compresses the array so that no "holes" are left, we can apply the template for processing all elements of an array:

smallestPos = 1
for j in range (2 to the number of elements currently in unsorted):
if unsorted[j] < unsorted [smallestPos]:
smallestPos = j

Copying the value thus found to sorted is easy:

sorted[k] = unsorted [smallestPos]

To remove it, we could shift all entries that follow it back one place in the array as was done to compress a Roman numeral in Is ItLegal? We encountered the same situation in The Shuffler's Dilemma and instead filled the gap by moving the last card in the deck to replace it. (Again, we don't care about the order of values in unsorted, since we're sorting them.) This technique requires that we keep track of the number of elements currently in unsorted, and leads to the following code:

def SelectionSort (unsorted, sorted):
k = 1
j = 2
unsortedSize = The number of array elements
for k = 1 to the number of array elements:
smallestPos = 1
for j = 2 to unsortedSize:
if unsorted[j] < unsorted [smallestPos]:
smallestPos = j
sorted[k] = unsorted [smallestPos]
unsorted [smallestPos] = unsorted [unsortedSize]
unsortedSize = unsortedSize - 1

How does insertion sorting work?

A function called InsertionSort may be defined with the same arguments used for SelectionSort, namely an unsorted array and a sorted array. In pseudocode, the algorithm is as follows:

for k = 1 to the number of array elements:
find the position in sorted where unsorted[k]
should go
insert it there

In SelectionSort, we maintained a variable called unsortedSize that contained the current length of the unsorted array. Here, we might think it useful to maintain a variable to store the current length of the sorted array. We already have such a variable, however-the loop variable k is keeping track of this. (It's actually 1 larger than the quantity we want.) That allows the following refinement:

for k = 1 to the number of array elements:
find the position in the k-1 elements of sorted
where unsorted[k] should go
insert it there

Finding the position in sorted where unsorted[k] should go is just a search. We just finished a function to do an efficient binary search, so it makes sense to try to reuse the code.

How is the position for insertion determined?

Two small modifications must be made to the iterative Search function, namely the addition of the number of elements in the array as a parameter and the use of this parameter in place of the constant FOODLISTSIZE. (The recursive version would not need this modification; to use it, we would just call SearchHelper directly.) Another problem arises, however, when we observe that Search had not previously intended the position argument to make sense in case the search was unsuccessful. Some analysis is neccessary to figure out what to return.

Stop & Help

In the first call to Search in the insertion sort loop, the size of the array being searched is 0. Does this cause any problems?

Search for 1:
Set low to 1, high to 2, and middle to 1.
The item 1 is less than the middle element, so set high to 0,
causing the search loop to terminate.
Search for 3:
Set low to 1, high to 2, and middle to 1.
The item 3 is greater than the middle element, so set low to 2
and middle to 2.
The item 3 is less than the middle element, so set high to 1,
causing the search loop to terminate.
Search for 5:
Set low to 1, high to 2, and middle to 1.
The item 5 is greater than the middle element, so set low to 2
and middle to 2.
The item 5 is greater than the middle element, so set low to 3,
causing the search loop to terminate.

At the end of the search loop, we have the following values:

It appears that in case of an unsuccessful search, the value of low is the position value to return. (One can prove this mathematically.)

Code to insert the value into sorted once we know the position can be copied from the Space Text program. The code in the Python Code section results.

How is the code tested?

The new code may be tested in several ways. The safest approach is first to write driver programs to test them separately, then to install them individually into the You Forgot What You Ate code and test them there.

Testing

12.8 Consider the following variant of the binary search code.

while not found and (high >= low):
middle = (low + high) // 2
if Equal (line, foodList[middle]. foodName):
found = True
foodEntry = foodList[middle]
else if LessThan (line, foodList[middle]. foodName):
high = middle
else:
low = middle

Does it work correctly? If so, explain why. If not, provide an array and an item for which the code works incorrectly.

Analysis

12.9 Which improvement makes the biggest difference in running time-changing files to arrays, rewriting Equal, or incorporating binary search?

Testing

12.10 Suppose that you decide to incorporate the improvements into the program rather than test them separately first. In which order should they be added?

Analysis

12.11 For what values in a 63-element array containing the integers 1 through 63 does binary search make the most comparisons?

Analysis

12.12 What is the maximum number of comparisons made by SelectionSort to sort an array of N elements? What is the minimum number of comparisons it can make?

Analysis

12.13 How many comparisons does InsertionSort make to sort an array that contains the five elements 3, 1, 7, 4, 2 into increasing order?

Reflection

12.14 Explain why the recursive version of the binary search routine may be said to be more "elegant" than the iterative version. State criteria that could define elegance and say why the recursive version meets the criteria.

Improving the History File Editor and Adding a Food File Editor

How should the history file editor be improved?

In the same way an array was used to store the food file information internally, we can also use an array to store the history information while the user works with it. The Initialize function can fill the array, and either the main program or the ExecuteQuit function can write the information back to the file. We specifically planned for different history representations in the design of the history editor, so the change should be straightforward to implement.

Using an array to represent the history should address two defects of the editor. First, it will allow a user to undo errors. Before the history entries are written back to the file, the user can be asked to verify that the changes made in that editing session should be made permanent. Second, the new representation will speed up editing operations by eliminating the need to go back to the file on the disk.

There are two problems with using arrays. One is that, since all editing operations will be done in memory rather than on the disk file, a program crash will cause all the editing in the session to be lost. The other is inherent in the use of arrays-potentially the user will provide more data than the array has room to store. We make sure to point out these problems to Terry, and we include messages that warn the user when he or she is approaching the program's storage limits.

What will change in the program?

An examination of the program reveals that little in the program must change and that almost all changes will be limited to the nine subprograms in the history file operations section. First, a type must be defined for internal storage of the history entries; we redefine SequenceType to be an array of EntryType rather than a file. (If this internal structure is to be named history, the history file variable must be renamed. We'll call it historyFile.)

Initialize must be expanded to fill the internal history file from the external file and to warn the user about too much data. A subprogram must be added to write the array entries back to the file, after checking with the user. We'll call this subprogram Terminate and call it in ExecuteQuit in order to be able to continue reading commands if the user doesn't want to update the file.

Changes to Find, Insert, Delete, PrintAll, and PrintUpTo use code we've used already in other case studies. Find can use the binary search code we designed earlier. All we need is functions LessThan and Equal that compare two dates; the program already includes functions AtOrBefore and Same that will suffice for this purpose. We must remember that history entries are stored in reverse order; this has already been a source of bugs. Insert and Delete apply templates for inserting and deleting array elements that were introduced in Space Text and Is It Legal? Insert must in addition include a check that the history structure is not too full. PrintAll and PrintUpTo are virtually identical to each other.

The process of converting the program to use an array is straightforward since the design in You Forgot What You Ate anticipated that the history data structures would change. Anticipation of using an array even included passing a position variable as a parameter to data structure access routines. The changes are easier to make than those made to the food file structure, where such changes were not anticipated.

How will the food file editor be designed?

The food file editor will be almost exactly the same as the history file editor. It will allow the same operations: add or delete a food, list foods, help, and quit. Only the details of food input will be different. Neither program appears in the Python Code section. They are left for the reader to complete in study questions.

Modification

12.15 Complete the revisions to the history file editor.

Application

12.16 Which subprograms in the history file editor will not be needed in the food file editor?

Application

12.17 Which subprograms in the history file editor will need to be modified for inclusion in the food file editor?

Application

12.18 Which subprograms in the history file editor can be used in the food file editor?

Application

12.19 Implement the food file editor.

Modification

12.20 Implement an undo command with which the user can undo the most recent add, delete, or undo command.

Modification

12.21 Implement a history command that displays the add and delete commands executed in the current editing session on numbered lines, for example as follows:

[1] add 13-9-2020
[2] add 14-9-2020
[3] delete 15-9-2020

Modification

12.22 Implement an undo command that works together with the history facility from question 12.21. The undo command will take a single argument, the number of the add or delete command to undo. For example, given the example history in question 12.21, the command undo 3 would undo the delete 15-9-2020 command and restore the entry for 15-9-2020 to the history file. The undone command will then be removed from the list displayed by later history commands.

Outline of Design and Development Questions

These questions summarize the main points of the commentary.

Improvements to You Forgot What You Ate
What changes are desired?
How are the graphing routines changed?
How are good default graph bounds computed?
How is the code tested?
How can programs be made to run more quickly?
What good does rewriting code details do?
Where in the program will optimizing prove most beneficial?
How can the search for a food name be sped up?
How does the binary search algorithm work?
How can this algorithm be applied to the food information?
How should the food information file be sorted?
How does selection sorting work?
How does insertion sorting work?
How is the position for insertion determined?
How is the code tested?

Improving the History File Editor and Adding a Food File Editor
How should the history file editor be improved?
What will change in the program?
How will the food file editor be designed?

Programmers' Summary

This case study discusses three improvements to the collection of programs designed in You Forgot What You Ate:

• modification of the code to execute more efficiently
• redesign of the graphs to allow uniform comparison of results from multiple users
• addition of a food file editor

All the modifications are best organized by referring to the program call diagram. The graph redesign is easiest. It consists mainly of applying the "process every element of an array" template to compute the maximum and minimum values for fat and calories; these are used to determine the range of values over which the graph will be plotted, should the user decide not to specify them himself or herself.

In general, there are three ways to make code more efficient. One is to replace references to external files by in-memory processing using arrays, since the time required to read an element from a file is typically 1000 times the amount of time to access an element in an array. Another is to find code that is executed many times and rewrite it more concisely. A third is to replace an inefficient algorithm by an efficient algorithm.

Here, binary search replaces linear search. The binary search algorithm is used with an array whose elements are in order; it is "dividing and conquering" in a different setting. It works by repeatedly dividing the array in half and narrowing the search to one of the halves. The commentary presents both an iterative implementation and a recursive implementation, and it notes the particular importance of testing the code on the end elements of the array.

Before binary search can be used, the array must be sorted. Approaches described in The Shuffler's Dilemma to randomize array elements may also be applied to put them in order. The commentary describes sorting by selection and sorting by insertion (the latter also uses the binary search code); other approaches are considered in exercises.

The same approaches are used to improve the efficiency of the history file editor. These modifications are easier since we planned for them in the original design.

Finally, the commentary touches briefly on the design of an editor for the food file. A substantial amount of code from the history file editor can merely be copied for this application.

Making Sense of The Eating Club

Analysis, Reflection

12.23 Suppose that you are working with a partner to revise the You Forgot What You Ate programs. How would you divide the revisions between you and your partner so that the two of you have roughly equal tasks to perform?

Application

12.24 Write a function called Quicksort that implements the Quicksort algorithm. It makes use of the divide-and-conquer strategy of binary search as follows. As in binary search, the arguments to Quicksort specify the range of elements within an array that are to be sorted. An element is chosen from the range as a "divider element"-there are several ways to do this, such as choosing the first element or a random element-and the remaining elements in the range are arranged so that all elements less than the divider element precede it and all elements greater than the divider follow it. The diagram below illustrates the result of this process.

Then the elements smaller than the divider are Quicksorted recursively, as are the elements larger than the divider. As in binary search, the base case of the recursion is a range that consists of 0 elements.

Testing

12.25 Run experiments with the Quicksort function you wrote for question 12.24 to see how it compares in efficiency to SelectionSort and InsertionSort.

Analysis, Reflection

12.26 How many values should there be in a list before it seems reasonable to implement an efficient search? Explain how such a decision might be made.

Reflection

12.27 Explain how adding an efficient search will help the programmer debug the program and how it will interfere with debugging of the program.

Application

12.28 A modification of binary search called interpolation search more closely simulates what people do to look up a number in a phone book. It assumes that one can determine the approximate position of an entry in the array by doing some computation; for instance, one might guess that a name starting with S, the 19th letter, would be around 19/26 of the way through the array. Implement a search function based on this approach.

Analysis

12.29 Would the interpolation approach described in question 12.28 be more appropriate for the history file or the food file? Explain.

Testing

12.30 Add mutations to the programs designed in this case study, and get a fellow programmer to find them. What bugs are easiest to localize, and what bugs are most difficult? What aspects of the program make it easier or more difficult to find its bugs?

Modification

12.31 Describe a format for the history file that would allow the program to keep track of data for more than one person in the same file.

Application

12.32 Write a set of programs to keep track of a checking account. Your programs should allow the user to enter a check (checks are normally written in numerical order), to enter a deposit, to void a check, and to mark that the check has been cashed and returned. The user should also be able to determine the balance in his or her account, and to generate a monthly summary of expenses and deposits.

Linking to Previous Case Studies

Reflection

12.33 Suppose we had planned from the start to add an efficient search to the You Are What You Eat program. How would the earlier programs have been different?

Reflection

12.34 If you had been writing the programs for Erin, an experienced programmer, instead of for Terry, how would the earlier programs have been different?

Reflection

12.35 Which templates for manipulating the arrays have counterparts in templates for files, and which do not? Explain

Analysis

12.36 Suppose that the argument to the graph-printing functions were an array of arrays, each element of which represents a separate person's fat and calorie consumption. For example, Terry's fat and calorie data might be the first element of the array, Erin's the second and so forth. Each person's fat consumption is to be plotted on the same graph, using a different symbol; the same should be done for the calorie consumption. Would it be easier to use a line-by-line approach to generate the graph, or the graph-image approach mentioned in question 9.50?

Modification

12.37 Implement the graph-printing function described in question 12.36.

Reflection

12.38 Suppose you didn't have the time to make the modifications suggested by Terry, and a programmer friend of yours volunteered to do so. How would you explain the You Forgot What You Ate programs to your friend to provide him or her with sufficient background to make the revisions?

Further Revisions to the You Are What You Eat Program

class FoodInfoType:
numFoods = 0
foods = []
found = False
global foodInfo
class FoodEntryType1:
foodName = ''
fat = 0
calories = 0
global foodEntry1
foodInfo = FoodInfoType()

# Return true exactly when the characters in line match those in s.

def Equal(line, s):
if line == s:
Equal = True
else:
Equal = False
return Equal

""" Return true exactly when the characters in line represent a word that alphabetically precedes the word represented by the characters in s."""

def LessThan(line, s):
k = 0
match = True
if len(line) > 0:
while k < len(line) and line[k] == s[k]:
k += 1
if k == len(line):
match = True
else:
match = line[k] == s[k]
if match == False:
return ord(line[k]) < ord(s[k])
else:
k = len(line)
while match == True and k < len(s):
if s[k] != ' ':
match = False
else:
k += 1
return not match

""" Search for an entry in elements low through high of foodinfo whose name matches the name in line. If the search is successful, return the entry in foodEntry and return true in found. If the search is unsuccessful, return false in found. """

def SearchHelper(line: LineType, low: int, high: int):
global foodInfo
global foodEntry1
global found1
found = False
found1 = False
if high < low:
found = False
else:
middle = (low + high) // 2
found = Equal (line, foodInfo. foods[middle] .foodName)
if found:
foodEntry1 = foodInfo. foods[middle]
found1 = True
return found1
else:
if LessThan (line, foodInfo. foods[middle] .foodName):
SearchHelper (line, low, middle - 1)
else:
SearchHelper (line, middle + 1, high)

""" Search for an entry in foodinfo whose name matches the name in line. If the search is successful, return the entry in foodEntry and return true in found. If the search is unsuccessful, return false in found. """

def Search(line, foodEntry, found):
found = False
found = SearchHelper (line, 0, foodInfo .numFoods - 1)
global found1
if found1:
foodEntry ["foodName"] = foodEntry1. foodName
foodEntry ["fat"] = int (foodEntry1.fat)
foodEntry ["calories"] = int (foodEntry1 .calories)
if DEBUGFOOD:
print('*** checking ', foodEntry ["foodName"])
return found1

""" Fill recentHistory from the history file, and foodinfo from the food information file. """

def Initialize(historyFile, recentHistory):
numEntries = 0
dayNum = 0
entry = EntryType.copy()
today = DateType.copy()
readlndata()
for dayNum in range(HISTORYSIZE):
if DEBUGHISTORY:
print('*** from history: ')
print( recentHistory [dayNum]["date"])
print( ' fat = {} calories = {}'.format (recentHistory [dayNum] ["fat"], recentHistory [dayNum] ["calories"]))
next_date = FindSuccessor (recentHistory [HISTORYSIZE - 1]["date"], today)
print('The food data you are about to enter is assumed to be for ', end = '')
print("{} {} {}".format (next_date["day"], next_date["month"], next_date["year"]))
print('Quit this program and run the history file editor, if this is incorrect.')
global foodInfo
global foodEntry1
fname = open("foodInfo.txt", "rt")
for foodName in fname:
foodName = foodName.split()
fEntry = FoodEntryType1()
fEntry.foodName = foodName[0]
fEntry.fat = foodName[1]
fEntry.calories = foodName[2]
foodInfo .foods. append(fEntry)
foodInfo .numFoods += 1
fname.close()
if FILEINPUT:
ReadEntry (testEile, today)
else:
ReadEntry (historyFile, today)